# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/8 21:24
功能描述:
N 皇后问题 （回溯法）
问题背景
N 皇后问题是经典的回溯算法应用案例：在 N×N 的棋盘上放置 N 个皇后，使得任何两个皇后都不能处于同一行、同一列或同一斜线上，求所有可能的放置方案。
解决思想：回溯法
回溯法（Backtracking）是一种通过试错寻找问题解的方法：
1:从问题的初始状态出发，逐步尝试可能的选择（如放置皇后的位置）。
2:每一步选择后，判断是否满足约束条件（不冲突）。
3:若满足，则继续探索下一步；若不满足，则回退到上一步，尝试其他选择。
4:重复上述过程，直到找到所有合法解或遍历完所有可能。

N 皇后问题中，回溯法通过逐行放置皇后，每行仅放一个，利用约束条件（列、对角线不冲突）剪枝无效路径，高效寻找所有解。

"""

"""
代码说明
1:核心函数backtrack：
    用row控制当前处理的行（每行仅放一个皇后，避免行冲突）。
    用cols集合记录已用列，diagonals1（row-col）和diagonals2（row+col）记录已用对角线，快速判断冲突。
    若当前列合法，则递归处理下一行；否则跳过（剪枝）。
    递归返回后，撤销当前选择（pop和remove），尝试其他列（回溯过程）。
2:结果转换：当row == n时，将路径path（每行的皇后列索引）转换为可视化棋盘（如[1,3,0,2]对应 4 皇后的一个解）。

示例输出（4 皇后问题）

4皇后问题的所有解（共2个）：

解1：
..Q.
Q...
...Q
.Q..

解2：
.Q..
...Q
Q...
..Q.


总结
N 皇后问题通过回溯法高效求解，核心是逐行尝试 + 冲突剪枝 + 撤销选择。
回溯法适合解决 “约束满足问题”（如排列、组合、棋盘问题），通过剪枝减少无效搜索，比暴力枚举更高效。


提问：本例可以说是递归吗？回溯和递归的区别？

回答：可以说 N 皇后问题的实现使用了递归，但核心思想是回溯法。递归是实现回溯的常用手段，但二者本质不同，具体区别如下：

1. 递归（Recursion）：一种编程技术
递归是指函数直接或间接调用自身的编程方式，核心是 “将大问题分解为结构相同的子问题”，通过解决子问题来解决原问题。
特点：依赖 “终止条件” 避免无限循环，子问题与原问题结构一致。
作用：简化代码逻辑，常用于树遍历、分治算法等场景（如斐波那契数列、快速排序）。

2. 回溯（Backtracking）：一种算法思想
回溯是一种通过试错寻找解的策略，核心是 “尝试选择→检测合法性→不合法则回退（撤销选择）→尝试新选择”，本质是 “深度优先搜索 + 剪枝”。
特点：需要记录中间状态，通过 “撤销选择” 回退到上一步，避免无效路径的持续探索（剪枝）。
作用：适合解决 “约束满足问题”（如 N 皇后、子集和数独），即解需满足多个约束条件，且解空间较大的场景。

3. 回溯与递归的关系
回溯通常用递归实现：回溯过程中，“探索下一步” 可以通过递归调用实现（如 N 皇后中 “处理下一行” 的递归），递归的栈结构天然适合记录 “当前路径” 和 “回退点”。
但递归≠回溯：
递归是 “实现手段”，回溯是 “解题思想”。

递归可以用于非回溯场景（如阶乘计算：f(n) = n * f(n-1)，没有 “回退” 操作）。
回溯也可以不用递归实现（如用栈手动模拟递归过程），但递归更简洁。

举例说明（N 皇后问题）
递归的体现：函数backtrack(row, ...)在处理完当前行后，调用backtrack(row+1, ...)处理下一行，自身调用自身，直到row == n（终止条件）。
回溯的体现：当尝试某一列发现冲突时，通过path.pop()、cols.remove(col)等操作 “撤销选择”，回退到上一行，尝试其他列，这是回溯的核心逻辑。

总结
递归是 “函数调用自身” 的技术，是实现工具。
回溯是 “试错 + 回退” 的算法思想，常用于求解约束问题。
回溯常依赖递归实现，但二者本质不同：递归强调 “子问题分解”，回溯强调 “探索 - 检测 - 回退” 的过程。

"""


def solve_n_queens(n):
    """
    解决N皇后问题，返回所有合法的放置方案

    参数:
        n: 皇后数量（棋盘大小为n×n）
    返回:
        列表，每个元素为一个合法方案（用'.'表示空，'Q'表示皇后）
    """

    def backtrack(row, cols, diagonals1, diagonals2, path):
        """
        回溯函数：逐行放置皇后，记录冲突信息

        参数:
            row: 当前处理的行（从0开始）
            cols: 已放置皇后的列集合（避免同列冲突）
            diagonals1: 已占用的主对角线（行-列 为常数，避免同对角线冲突）
            diagonals2: 已占用的副对角线（行+列 为常数，避免同对角线冲突）
            path: 当前已放置的皇后位置（记录每行的列索引）
        """
        # 终止条件：所有行都放置了皇后，找到一个合法方案
        if row == n:
            # 将path转换为可视化棋盘（如[1,3,0,2]→["..Q.","Q...","...Q",".Q.."]）
            board = ['.' * col + 'Q' + '.' * (n - col - 1) for col in path]
            result.append(board)
            return

        # 尝试当前行的每一列（0到n-1）
        for col in range(n):
            # 计算当前位置的对角线标识
            d1 = row - col  # 主对角线：行-列 相同则冲突
            d2 = row + col  # 副对角线：行+列 相同则冲突

            # 剪枝：若列或对角线已被占用，则跳过当前列
            if col in cols or d1 in diagonals1 or d2 in diagonals2:
                continue

            # 选择当前列：记录冲突信息，更新路径
            cols.add(col)
            diagonals1.add(d1)
            diagonals2.add(d2)
            path.append(col)

            # 递归处理下一行
            backtrack(row + 1, cols, diagonals1, diagonals2, path)

            # 回溯：撤销选择，尝试其他列
            path.pop()
            diagonals2.remove(d2)
            diagonals1.remove(d1)
            cols.remove(col)

    # 存储所有合法方案
    result = []
    # 从第0行开始回溯，初始状态无冲突
    backtrack(0, set(), set(), set(), [])
    return result


# 示例：求解4皇后问题
if __name__ == "__main__":
    n = 4
    solutions = solve_n_queens(n)
    print(f"{n}皇后问题的所有解（共{len(solutions)}个）：")
    for i, sol in enumerate(solutions, 1):
        print(f"\n解{i}：")
        for row in sol:
            print(row)